#define _CRT_SECURE_NO_WARNINGS

//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    struct ListNode* ptail1 = headA;
//    struct ListNode* ptail2 = headB;
//    int count1 = 1;
//    int count2 = 1;
//    while (ptail1)
//    {
//        ptail1 = pati1->next;
//        count1++;
//    }
//    while (ptail2)
//    {
//        ptaill2 = ptail2->next;
//        count2++;
//    }
//
//
//    if (ptail1 != ptail2)
//    {
//        rettrun NULL;
//    }
//    else
//    {
//        struct ListNode* plong = headA;
//        struct ListNode* pshort = headB;
//        int gap = count1 - count2;
//        if (count2 > count1)
//            gap = count2 - count1;
//        if (count2 > count1)
//        {
//            plong = headB;
//            pshort = headA;
//        }
//        while (gap--)
//        {
//            plong = plong->next;
//        }
//        while (1)
//        {
//            if (plong == pshort)
//            {
//                return plong;
//            }
//            plong = plong->next;
//            pshort = pshort->next;
//        }
//    }
//
//}
//
//
//
//
//bool hasCycle(struct ListNode* head) {
//    struct ListNode* fast = head;
//    struct ListNode* slow = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//            return true;
//    }
//    return false;
//}
//
//
//
//
//bool hasCycle(struct ListNode* head) {
//    struct ListNode* fast = head;
//    struct ListNode* slow = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//            return true;
//    }
//    return false;
//}
//struct ListNode* detectCycle(struct ListNode* head) {
//    if (hasCycle(head))
//    {
//        struct ListNode* fast = head;
//        struct ListNode* slow = head;
//        struct ListNode* meet = NULL;
//        struct ListNode* pcur = head;
//        while (1)
//        {
//            fast = fast->next->next;
//            slow = slow->next;
//            if (slow == fast)
//            {
//                meet = fast;
//                break;
//            }
//        }
//        while (pcur != meet)
//        {
//            pcur = pcur->next;
//            meet = meet->next;
//        }
//        return meet;
//    }
//    return NULL;
//}
//
//
//
//struct Node* copyRandomList(struct Node* head) {
//    if (head == NULL)
//        return NULL;
//    struct Node* pcur = head;
//    struct Node* copy = NULL;
//    struct Node* newhead = NULL;
//    while (pcur)
//    {
//        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
//        newnode->val = pcur->val;
//        newnode->random = NULL;
//        newnode->next = pcur->next;
//        pcur->next = newnode;
//        pcur = newnode->next;
//    }
//    pcur = head;
//    copy = head->next;
//    newhead = copy;
//    while (pcur)
//    {
//        if (pcur->random)
//            copy->random = pcur->random->next;
//        pcur = copy->next;
//        if (pcur)
//            copy = pcur->next;
//    }
//    pcur = head;
//    copy = head->next;
//    while (pcur)
//    {
//        pcur->next = copy->next;
//        pcur = pcur->next;
//        if (pcur)
//        {
//            copy->next = pcur->next;
//            copy = copy->next;
//        }
//        else
//        {
//            copy->next = NULL;
//        }
//
//    }
//    return newhead;
//}